Міністерство освіти і науки України Національний університет « Львівська політехніка» кафедра будівельної механіки / Розрахунково-графічна робота №3 з дисципліни: « Основи системного анілізу» Варіант №1  Львів 2013 Задано: Необхідно знайти мінімальне значення функції   F = -2x1+2x2 → min, при такій системі обмежень: 2x1+4x2≤8 (1) -6x1-3x2≤-4 (2) x1-2x2≤2 (3) 3x1+x2≤6 (4) x1≥0 (5) x2≥0 (6) Графічний метод розв’язку задачі. Будуємо графіки прямих вище заданих рівнянь. / Перетин півплощин буде являти собою область, всі точки якої є розв’язками відповідної нерівності. Розглянемо функцію F = -2x1+2x2 → min. Побудуємо пряму, яка відповідає значенню функції  F = 0, F = -2x1+2x2 = 0. Так утворилась лінія рівня яка паралельно пересувається в напрямку вектора до збігу з крайньою точкою многокутника. Початок вектора – точка (0; 0), кінець – точка (-2; 2).На графіку ця пряма позначена пунктирною лінією. / / Пряма F(x) = const  перетинає область в точці F. Так як точка F отримана в результаті перетину прямих. То її координати задовольняє система рівнянь цих прямих: x1-2x2≤23x1+x2≤6Розв’язуємо цю систему рівнянь і отримуємо координати точки: x1 = 2, x2 = 0 Звідси знаходимо мінімальне значення цільової функції: Fmin(X) =   -2*2 + 2*0 = -4 Відповідь: Fmin= -4. Симплекс метод Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних ( перехід до канонічної форми ) . У 1 -му нерівність сенсу ( ≤ ) вводимо базисну змінну x3 . У 2 -му нерівність сенсу ( ≥) вводимо базисну змінну x4 зі знаком мінус. У 3 -му нерівність сенсу ( ≤ ) вводимо базисну змінну x5 . У 4 -му нерівність сенсу ( ≤ ) вводимо базисну змінну x6 . 2x1 + 4x2 + 1x3 + 0x4 + 0x5 + 0x6 = 86x1 + 3x2 + 0x3-1x4 + 0x5 + 0x6 = 41x1-2x2 + 0x3 + 0x4 + 1x5 + 0x6 = 23x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 = 6 Введемо штучні змінні x : в 2 -му рівність вводимо змінну x7 ; 2x1 + 4x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 86x1 + 3x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 41x1-2x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 23x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 = 6 Для постановки задачі на мінімум цільову функцію запишемо так : F(X) = -2x1+2x2+Mx7 → min Отриманий базис називається штучним , а метод рішення називається методом штучного базису . З рівнянь виводимо штучні змінні: x7 = 4-6x1-3x2+x4, які підставимо в цільову функцію: F(X) = -2x1 + 2x2 + M(4-6x1-3x2+x4) → min, або F(X) = (-2-6M)x1+(2-3M)x2+(M)x4+(4M) → min Вирішимо систему рівнянь щодо базисних змінних: x3 , x7 , x5 , x6 , Базис B x1 x2 x3 x4 x5 x6 x7  x3 8 2 4 1 0 0 0 0  x7 4 6 3 0 -1 0 0 1  x5 2 1 -2 0 0 1 0 0  x6 6 3 1 0 0 0 1 0  F(X0) 4M 2+6M -2+3M 0 -M 0 0 0   Переходимо до основного алгоритму симплекс - методу . Ітерація №0 1 . Перевірка критерію оптимальності . Поточний опорний план неоптимальний , тому що в індексному рядку знаходяться позитивні коефіцієнти . 2 . Визначення нової базисної змінної. В якості ведучого виберемо стовпець , відповідний змінної x1 , так як це найбільший коефіцієнт . 3 . Визначення нової вільної змінної. Обчислимо значення Di по рядках як частка від ділення : bi / ai1 і з них виберемо найменше : min (8 : 2 , 4 : 6 , 2 : 1 , 6 : 3 ) = 2/3 Отже , 2 - ий рядок є ведучий. Базис B x1 x2 x3 x4 x5 x6 x7 min  x3 8 2 4 1 0 0 0 0 4  x7 4 6 3 0 -1 0 0 1   x5 2 1 -2 0 0 1 0 0 2  x6 6 3 1 0 0 0 1 0 2  F(X1) 4M 2+6M -2+3M 0 -M 0 0 0 0   4 . Перерахунок симплекс - таблиці. Формуємо наступну частину симплексного таблиці. Замість змінної x7 в план 1 увійде змінна x1. Рядок , відповідна змінної x1 в плані 1 , отримана в результаті поділу всіх елементів рядка x7 плану 0 на дозволяючий елемент РЕ = 6 На місці дозволяє елемента в плані 1 отримуємо 1 . В інших клітинах стовпця x1...